#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        int carry = 0;                                 
        ListNode *res = NULL, *head;
        int sum = 0;

        while (l1 && l2) {
           sum = l1->val + l2->val + carry;
//           cout << l1->val << " " << l2->val << " " << sum << endl;
           if (sum > 9) {sum -= 10; carry = 1;}
           else carry = 0;
           ListNode *newnode = new ListNode(sum);
           if (!res) {res = newnode; head = res;}
           else {res->next = newnode; res = newnode;} 
           l1 = l1->next;
           l2 = l2->next;
        }
        
        ListNode *left = l1 ? l1 : l2;

        while (left) {
           sum = left->val + carry;
//           cout << sum << endl;
           if (sum > 9) {sum -= 10; carry = 1;}
           else carry = 0;
           ListNode *newnode = new ListNode(sum);
           if (!res) {res = newnode; head = res;}
           else {res->next = newnode; res = newnode;} 
           left = left->next;
        }

        //this is very important case that may be missed
        if (carry != 0) {
            ListNode *newnode = new ListNode(1);
            if (!res) {res = newnode; head = res;}
            else {res->next = newnode; res = newnode;} 
        } 

        return head; 
    }
};

void printlist(ListNode *list)
{
    while (list) {
        cout << list->val << " ";
        list = list->next;
    }
    cout << endl;
}

//add the best code
   ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode dummy(0);
        ListNode *head = &dummy;
        int carry = 0;
        while(l1 || l2) {
           int a = l1 ? l1->val : 0;
           int b = l2 ? l2->val : 0;
           int sum = a + b + carry;
           carry = sum/10;
           sum = sum%10;
           head->next = new ListNode(sum);
           head = head->next;
           // bug again. check the pointer
           if (l1) l1 = l1->next;
           if (l2) l2 = l2->next;
        }   
        if (carry)
            head->next = new ListNode(1);
        ListNode *cur = dummy.next;

        while(cur) {
            cout << cur->val << " ";
            cur = cur->next;
        }   
            
        return dummy.next;
    }   


int main(int argc, char **argv)
{
    Solution mySolution;
    ListNode *aList = new ListNode(2);
//    aList->next = new ListNode(4);
//    aList->next->next = new ListNode(3);
  //  aList->next->next->next = new ListNode(5);
//    aList->next->next->next->next = new ListNode(3);
    printlist(aList);

    ListNode *bList = new ListNode(5);
    bList->next = new ListNode(6);
    bList->next->next = new ListNode(4);
    printlist(bList);

    cout << "---------------" << endl;

    ListNode *result = mySolution.addTwoNumbers(aList, bList); 
    printlist(result);
    
    return 0;
}
